#include "randnum.h"
#include <windows.h>
#include <sortthread.h>
#include <iostream>
using namespace std;

/*两组归并函数*/
/*
定义的三个整型变量i，j，k
i用来遍历归并的前一个有序数列，其初始位置是low
j用来遍历归并的后一个有序序列，其初始值是u+1
k用来指出归并后得到的有序序列末尾元素位置，初始值数low
遍历完其中一个有序序列后，只需把另一个未结束的有序序列剩余元素复制到合并的有序序列末尾
*/
void SortThread::merge(RecordNode *r, RecordNode *r1, int low, int m, int high)
{
    sortTle++;
    this->sendt(sortTle,sortMov,sortCmp);
    int i = low, j = m + 1, k = low;
    while (i <= m && j <= high)
    {
        if (r[i].key <= r[j].key)
        {
            sortCmp++;
            this->sendt(sortTle,sortMov,sortCmp);
            r1[k++] = r[i++];
            sortMov++;
            for(int ii =0; ii < this->size; ii++)
            {
                catched1=i;
                this->sendArray[ii] =  r1[ii].key;
            }
            this->senda(catched1,-1);
        }
        else
        {
            sortCmp++;
            this->sendt(sortTle,sortMov,sortCmp);
            r1[k++] = r[j++];
            sortMov++;
            for(int ii =0; ii < this->size; ii++)
            {
                catched1=i;
                this->sendArray[ii] =  r1[ii].key;
            }
            this->senda(catched1,-1);
        }
        for(int ii =0; ii < this->size; ii++)
        {
            catched1=i;
            this->sendArray[ii] =  r1[ii].key;
        }
        this->senda(catched1,-1);
    }
    this->senda(catched1,-1);
    while (i <= m)
    {
        sortCmp++;
        this->sendt(sortTle,sortMov,sortCmp);
        r1[k++] = r[i++];
        sortMov++;
        for(int ii =0; ii < this->size; ii++)
        {
            catched1=i;
            this->sendArray[ii] =  r1[ii].key;
        }
        this->senda(catched1,-1);
    }
    while (j <= high)
    {
        sortCmp++;
        this->sendt(sortTle,sortMov,sortCmp);
        r1[k++] = r[j++];
        sortMov++;
        for(int ii =0; ii < this->size; ii++)
        {
            catched1=j;
            this->sendArray[ii] =  r1[ii].key;
        }
        this->senda(catched1,-1);
    }
    this->sendt(sortTle,sortMov,sortCmp);
    this->senda(catched1,-1);
}

/*一趟归并扫描算法，取length为本趟归并的有序子文件的长度*/
/*
参加排序的序列已经有序，多次调用两组归并算法将所有两两相邻成对的子序列合并成若干长度为2*length的有序子序列
若某一趟归并扫描到最后剩下的元素个数不足两个子序列的长度时：
1.若剩下的元素个数大于一个子序列的长度length时，则再调用一次两组归并算法merge将剩下的两个不等长的子序列合并成一个有序子序列
2.若剩下的元素个数小于或者等于一个子序列的长度 t 时，只须将剩下的元素依次复制到前一个子序列后面
*/
void SortThread::mergePass(RecordNode *r, RecordNode *r1, int n, int length)
{
    int i = 0, j;
    while (i + 2 * length - 1 < n)
    {
        merge(r, r1, i, i + length - 1, i + 2 * length - 1);
        i += 2 * length;
    }
    if (i + length - 1 < n - 1)
    {
        merge(r, r1, i, i + length - 1, n - 1);
    }
    else
    {
        for (j = i; j < n; j++)
        {
            sortCmp++;
            this->sendt(sortTle,sortMov,sortCmp);
            r1[j] = r[j];
            //Sleep(frd);
            for(int ii =0; ii < this->size; ii++)
            {
                catched1=j;
                this->sendArray[ii] =  r1[ii].key;
            }
            this->senda(catched1,-1);
        }
    }
}

/*二路归并排序函数*/
/*传入参数**SortObject数组***/
/*递归调用SortPass与merge*/
void SortThread::mergeSort(SortObject *pvector)
{
    RecordNode record[1000];
    sortTle = 0;
    sortMov = 0;
    sortCmp = 0;
    for(int i = 0; i<1000; i++)
    {
        record[i].key = sendArray[i];
    }
    int length = 1;
    pvector->n = this->size;
    while (length < pvector->n)
    {
        sortCmp++;
        mergePass(pvector->record, record, pvector->n, length);
        length *= 2;
        this->senda(catched1,-1);
        sortCmp++;
        mergePass(record, pvector->record, pvector->n, length);
        length *= 2;
        this->senda(catched1,-1);
    }
    for(int i = 0; i < size; i++)
    {
        senda(i,-10);
    }
}
